Multi-operand adders that calculate the summation of more than two operands usually consist of compressor trees, which reduce the number of operands to two without any carry propagation, and carry-propagate adders for the two operands in the ASIC implementation. Compressor trees that consist of full adders and half adders cannot be implemented efficiently on LUT-based FPGAs, and carry-chains or dedicated structures have been utilized to produce multi-operand adders on FPGAs. Recent studies indicate that compressor trees can be implemented efficiently on LUTs using Generalized Parallel Counters (GPCs) as the building blocks of compressor trees. This paper addresses the problem of synthesizing compressor trees based on GPCs. Based on the observation that characteristics such as the area, power, and delay correlate roughly to the total number and the maximum level of GPCs, the target problem can be regarded as a minimization problem for the total number of GPCs and the maximum levels of the GPCs, for which an ILP-based approach is proposed. The key point of our formulation is not to model the problem based on the structures of compressor trees like the existing approach, but instead the compression process itself is used to reduce the number of variables and constraints in the ILP formulation. The experimental results demonstrate the advantage of our formulation in terms of the quality and runtime.

This paper proposes a test scheduling method for stuck-at faults in a CHAIN interconnect, which is an asynchronous on-chip interconnect architecture, with scan ability. Special data transfer which is permitted only during test, is exploited to realize a more flexible test schedule than that of a conventional approach. Integer linear programming (ILP) models considering such special data transfer are developed according to the types of modules under test in a CHAIN interconnect. The obtained models are processed by using an ILP solver. This framework can not only obtain optimal test schedules but also easily introduce additional constraints such as a test power budget. Experimental results using benchmark circuits show that the proposed method can reduce test application time compared to that achieved by the conventional method.

This study formulates and solves the wire planning problem with electro-migration and interference using an effective integer linear programming (ILP)-based approach. For circuits without obstacles, the proposed approach obtains a wire planning with the minimum wiring area. An effective approach for estimating the length of feasible routing wire is proposed to handle circuits with obstacles. In addition, the space reservation technique, which allocates the ring of the free silicon space around obstacles, is presented to improve interference among routing wires and on-obstacle wires. For circuits with obstacles, the proposed method minimizes total wiring area and reduces interference. Experimental results show that the integer linear-programming-based approach effectively and efficiently minimizes wiring area of routing wires.

For recent and future nanometer-technology VLSIs, static and dynamic delay variations become a serious problem. In many cases, the hold timing constraint, as well as the setup timing constraint, becomes critical for latching a correct signal under delay variations. While the timing violation due to the fail of the setup timing constraint can be fixed by tuning a clock frequency or using a delayed latch, the timing violation due to the fail of the hold timing constraint cannot be fixed by those methods in general. Our approach to delay variations (in particular, the hold timing constraint) proposed in this paper is a novel register assignment strategy in high-level synthesis, which guarantees safe clocking by Backward-Data-Direction (BDD) clocking. One of the drawbacks of the proposed register assignment is the increase in the number of required registers. After the formulation of this new register minimization problem, we prove NP-hardness of the problem, and then derive an integer linear programming formulation for the problem. The proposed method receives a scheduled data flow graph, and generates a datapath having (1) robustness against delay variations, which is ensured by BDD-based register assignment, and (2) the minimum possible number of registers. Experimental results show the effectiveness of the proposed method for some benchmark circuits.

Multiple supply voltage (MSV) assignment is a highly effective means of reducing power consumption. Many existing algorithms perform very well for power reduction. However, they do not handle the area issue of level shifters. In some cases, although one gets a superior result to reduce the power consumption, but many extra level shifters are needed to add so that the circuit area will be over the specification. In this paper, we present an effective integer linear programming (ILP)-based MSV assignment approach to solve two problems with different objectives. For the objective of power reduction under timing constraint, compared with GECVS algorithm, the power consumption obtained by our proposed approach can be further reduced 0 to 5.46% and the number of level shifters is improved 16.31% in average. For the objective of power reduction under constraints of both timing and area of level shifters, the average improvement of power consumption obtained by our algorithm is still better than GECVS while reducing the number of level shifters by 22.92% in average. In addition, given a constraint of total power consumption, our algorithm will generate a design having minimum circuit delay. Experimental results show that the proposed ILP-based MSV assignment algorithm solves different problems flexibly.

This paper proposes an Integer Linear Programming (ILP)-based power minimization method by partitioning into regions, first, with three different VDD's(PM3V), and, secondly, with two different VDD's(PM2V). To reduce the solving time of triple-VDD case (PM3V), we also proposed a partitioned ILP method(p-PM3V). The proposed method provides 29% power saving on the average in the case of triple-VDD compared to the case of single VDD. Power reduction of PM3V compared to Clustered Voltage Scaling (CVS) was about 18%. Compared to the unpartitioned ILP formulation(PM3V), the partitioned ILP method(p-PM3V) reduced the total solution time by 46% at the cost of additional power consumption within 1.3%.

For recent and future nanometer-technology VLSIs, static and dynamic delay variations become a serious problem. In many cases, the hold constraint, as well as the setup constraint, becomes critical for latching a correct signal under delay variations. This paper treats the hold constraint in a datapath circuit, and discusses a register assignment in high level synthesis considering delay variations. Our approach to ensure the hold constraint under delay variations is to enlarge the minimum-path delay between registers, which is called minimum-path delay compensation (MDC) in this paper. MDC can be done by inserting delay elements mainly in non-critical paths of a functional unit (FU). One of our contributions is to show that the minimization of the number of minimum-path delay compensated FUs is NP-hard in general, and it is in the class P if the number of FUs is a constant. A polynomial time algorithm for the latter is also shown in this paper. In addition, an integer linear programming (ILP) formulation is also presented. The proposed method generates a datapath having (1) robustness against delay variations, which is ensured partly by MDC technique and partly by SRV-based register assignment, and (2) the minimum possible numbers of MDCs and registers.

In the context of multiple constant multiplication (MCM) design, we propose a novel common sub-expression elimination (CSE) algorithm that models the optimal synthesis of coefficients into a 0-1 mixed-integer linear programming (MILP) problem with a user-defined generic logic depth constraint. We also propose an efficient solution space, which combines all minimal signed digit (MSD) representations and the shifted sum (difference) of coefficients. In the examples we demonstrate, the combination of the proposed algorithm and solution space gives a better solution comparing to existing algorithms.

In a power grid used to distribute electricity, optical fibers can be inserted inside overhead ground wires to form an optical network infrastructure for data communications. Dense wavelength division multiplexing (DWDM)-based optical networks present a promising approach to achieve a scalable backbone network for power grids. This paper proposes a complete optimization procedure for optical network designs based on an existing power grid. We design a network as a subgraph of the power grid and divide the network topology into two layers: backbone and access networks. The design procedure includes physical topology design, routing and wavelength assignment (RWA) and optical amplifier placement. We formulate the problem of topology design into two steps: selecting the concentrator nodes and their node members, and finding the connections among concentrators subject to the two-connectivity constraint on the backbone topology. Selection and connection of concentrators are done using integer linear programming (ILP). For RWA and optical amplifier placement problem, we solve these two problems together since they are closely related. Since the ILP for solving these two problems becomes intractable with increasing network size, we propose a simulated annealing approach. We choose a neighborhood structure based on path-switching operations using k shortest paths for each source and destination pair. The optimal number of optical amplifiers is solved based on local search among these neighbors. We solve and present some numerical results for several randomly generated power grid topologies.

At the behavioral level, large power savings are possible by shutting down unused operations, which is commonly referred to as power management. However, operation scheduling has a significant impact on the potential for power saving via power management. In this paper, we present an integer linear programming (ILP) model to formally formulate the simultaneous application of operation scheduling and power management in high level synthesis. Our objective is to maximize the power saving under both the timing constraints and the resource constraints. Note that our approach guarantees solving the problem optimally. Compared with previous work, experimental data consistently show that our approach has significant relative improvement in the power savings.

A Multi-Functional unit has several functions and these can be changed with a control signal. For High-Level Synthesis, using Multi-Functions units in operation chaining make it possible to obtaining the solution with the same number of control steps and less resources compared to that without them. This paper proposes an operation chaining method considering Multi-Functional units. The method formulates module selection, scheduling, and functional unit allocation with operation chaining as a 0/1 integer linear problem and obtains optimal solution with minimum number of control steps under area and clock-cycle type constraints. The first contribution of this paper is to propose the global search for operation chaining with Multi-Functional units having multiple outputs as well as with single output. The second contribution is to condier the area constraint as a resource constraint instead of the type and number of functional units. Experimental results show that chaining with Multi-Functional units is effective and the proposed method is useful to evaluate heuristic algorithms.

With the advent of deep sub-micron era, there is a demand to consider the design closure problem in high-level synthesis. It is well known that the slack is an effective means of tolerating the uncertainties in operation delays. Previous work ever attempted to increase the usable slack based on a given initial schedule. Instead of the post-processing approach, this paper is the first attempt to the simultaneous application of operation scheduling and slack optimization. We use a 0-1 integer linear programming (0-1 ILP) approach to formally formulate the problem. Under the design constraints (timing and resource), our approach is applicable to two different objective functions: the maximization of the total usable slack and the maximization of the number of non-zero slack operations. Compared with previous work, our approach has the following two advantages: first, our approach guarantees the optimality; second, our approach is more suitable for the design space exploration.

We propose a cell library development methodology for throughput enhancement of character projection equipment. First, an ILP (Integer Linear Programming)-based cell selection is proposed for the equipment for which both of the CP (Character Projection) and VSB (Variable Shaped Beam) methods are available, in order to minimize the number of electron beam (EB) shots, that is, time to fabricate chips. Secondly, the influence of cell directions on area and delay time of chips is examined. The examination helps to reduce the number of EB shots with a little deterioration of area and delay time because unnecessary directions of cells can be removed. Finally, a case study is shown in which the numbers of EB shots are shown for several cases.

In this paper, a new Mixed Integer Linear Programming algorithm is proposed to resolve the light-tree routing and wavelength assignment with wavelength continuity constraints. The node in our system is limited branching and power-efficient multicast capable OXC. Numerical results are given and discussed to show the efficiency of our algorithm.

In this paper, we consider the problem of multicast routing and wavelength assignment (MC-RWA) in multi-fiber all-optical WDM networks. Two main network design system comprehensively investigated here are mesh and multi-ring designs. Given the multicast traffic demands, we present new ILP formulations to solve the MC-RWA problem with an objective to determine the minimal number of fibers needed to support the multicast requests. Unlike previous studies, our ILP formulations are not only capable of finding the optimal multicast routing and wavelength assignment pattern to the light-trees, but also finding the optimal light-tree structures simultaneously. Since broadcast and unicast communications are special cases of multicast communications, our ILP models are actually the generalized RWA mathematical models of optical WDM networks. In addition to proposing the ILP models, this paper takes two main issues affecting the network capacity requirement into account, that is, the splitting degree level of optical splitters and techniques of wavelength assignment to the light-trees. Three multicast wavelength assignment techniques studied in this paper are Light-Tree (LT), Virtual Light-Tree (VLT) and Partial Virtual Light-Tree (PVLT) techniques. Due to the NP-completeness of the MC-RWA problem, the ILP formulations can reasonably cope with small and moderate networks. To work with large networks, this paper presents alternative MC-RWA ILP-based heuristic algorithms for the PVLT and LT networks and develops lower bound techniques to characterize the performance of our algorithms. Using existing large backbone networks, numerical results are reported to analyze such aspects as multiple fiber systems, the benefits of using optical splitters and wavelength converters, and the capacity difference between the mesh and multi-ring designs. Finally, this paper provides an analysis of the influence of network connectivity on the network implementation under the constraints of mesh and multi-ring design schemes.

We present a new approach to the loop scheduling problem, which excels previous solutions in two important aspects: The resource constraints are formulated using flow graphs, and the initiation interval λ is treated as a rational variable. The approach supports heterogeneous processor architectures and pipelined functional units, and the Integer Linear Programming implementation produces an optimum loop schedule, whereby a minimum λ is achieved. Our flow graph model facilitates the cyclic binding of loop operations to functional units. Compared to previous research results, the solution can provide faster loop schedules and a significant reduction of the problem complexity and solution time.

The forwarding speed of IP routers must grow to accommodate the skyrocketing amount of traffic on the Internet. MPLS, which relies on the high processing power of lower layers, is a solution and it is under developing. On the other hand, a WDM network has been expected as a high-speed network, but it is also called a stupid network because of lacking its traffic granularity. In order to bridge between these two layers, an IP over WDM network by a concept of MPLS has been proposed. This network has a potential to effectively use large transmission capacity provided by WDM technology. In this paper, we design IP over WDM networks that reconfigure IP routing and lightpaths each day or month. We formulate a problem that maximizes the network throughput based on integer linear programming. Through numerical examples, we show that the increase of the network throughput in IP over WDM networks is larger than that of IP networks. We also show the area where this method is applicable to the reconfigurable network.

In a recent paper, Yang proposes an integer labeling algorithm for determining whether an arbitrary simplex P in Rn contains an integer point or not. The problem under consideration is a very difficult one in the sense that it is NP-complete. The algorithm is based on a specific integer labeling rule and a specific triangulation of Rn. In this paper we discuss a practical implementation of the algorithm and present a computer program (ILIN) for solving integer programming using integer labeling algorithm. We also report on the solution of a number of tested examples with up to 500 integer variables. Numerical results indicate that the algorithm is computationally simple, flexible, efficient and stable.

This paper presents an efficient optimal block terminal assignment algorithm based on the integer programming for a data path synthesis. The problem is to assign buses to commutable terminals on functional units such that the number of buses is minimum, when the scheduling and allocation of operations and registers have been done. Three methods are used in the algorithm to decrease the amount of computation.

This paper presents a new timing-driven global routing method for standard cell layout. The proposed method can explicitly consider the timing constraint between two registers and minimize the channel density under the given timing constraint. In the proposed method, first, we determine the initial global routes. Next, we improve the global routes to satisfy the timing constraint between two registers as well as to minimize the channel density. Finally, for each cell row, the nets incident to terminals on the cell row are assigned to channels to minimize the channel density using 0-1 integer linear programming. We also show the experimental results of the proposed method implemented on an engineering workstation. Experimental results show that the proposed method is quite promising.